/*
题目 : 最长理想子序列
给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

    t 是字符串 s 的一个子序列。
    t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。
注意：字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-ideal-subsequence
*/
public class LongestIdealString {
    // 最终优化版
    public int longestIdealString(String s, int k) {
        // 表示以 i 元素为结尾的最长理想子串
        int[] dp = new int[26];
        dp[s.charAt(0) - 'a'] = 1;

        int n = s.length();
        int maxLength = 1;
        for (int i = 1; i < n; i++) {  // 每一轮都是搜索以 i 元素结尾的理想子串
            int cur = s.charAt(i) - 'a';
            // 再搜索可能是答案的区间
            for (int j = 0; j <= k; j++) {
                int up = cur - j;
                int down = cur + j;
                // 不能直接在取最大值中 +1, 否则可能连加两次
                if (up >= 0 && up < 26) {
                    dp[cur] = Math.max(dp[cur], dp[up]);
                }
                if (down >= 0 && down < 26) {
                    dp[cur] = Math.max(dp[cur], dp[down]);
                }
            }
            dp[cur] ++;
            maxLength = Math.max(maxLength, dp[cur]);
        }

        return maxLength;
    }


    // 优化版
    public int longestIdealString1(String s, int k) {
        int n = s.length();

        // 表示以 i 元素为结尾的最长理想子串
        int[] dp = new int[n];
        dp[0] = 1;

        // 表示 i 元素前以 Character 字符结尾的最长理想子串
        Map<Character, Integer> map = new HashMap<> ();
        map.put(s.charAt(0), 1);
        int maxLength = 1;
        for (int i = 1; i < n; i++) {  // 每一轮都是搜索以 i 元素结尾的理想子串
            char cur = s.charAt(i);
            // 再搜索可能是答案的区间
            for (int j = 0; j <= k; j++) {
                char up = (char) (cur + j);
                char down = (char) (cur - j);

                dp[i] = Math.max(dp[i], map.getOrDefault(up, 0) + 1);
                dp[i] = Math.max(dp[i], map.getOrDefault(down, 0) + 1);
            }
            // 更新以 i 元素为结尾的最长理想子串
            maxLength = Math.max(maxLength, dp[i]);
            map.put(cur, dp[i]);
        }

        return maxLength;
    }

    // 无优化版, 超时
    public int longestIdealString2(String s, int k) {
        // 子序列非连续
        int n = s.length();
        int maxLength = 1;

        // 以 i 元素结尾的理想字符串的长度
        int[] dp = new int[n];
        dp[0] = 1;

        // 以 i 元素为结尾的字符串k
        for (int i = 1; i < n; i++) {
            dp[i] = 1; // 以 i 结尾的字符串最短长度为 1
            for (int j = 0; j < i; j++) {
                if (Math.abs(s.charAt(i) - s.charAt(j)) <= k) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }
}
